// m

// 给定两个整数m和n，代表大小为m*n的棋盘，一个机器人位于棋盘左上角的位置，机器人每次只能向右，或者向下移动一步
// 机器人试图达到网格的右下角，但是网格中有障碍物，不能通过
// 现在给定一个二维数组表示网格，1代表障碍物，0代表空位，要求计算出：从左上角到右下角会有多少条不同的路径

// 解题思路： 动态规划
// 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1],因为只能往一个方向走，dp[i][0] = 1, dp[0][j] = 1,如果在第一行，第一列遇到障碍，则终止赋值，跳出循环
// 然后从上到下，从左到右依次遍历，递推求解，遇到障碍物就跳过，最终输出dp[m-1][n-1]

function uniquePathsWithObstacles(obstacleGrid) {
    let m = obstacleGrid.length
    let n = obstacleGrid[0].length
    let dp = new Array(m).fill(0).map(() => new Array(n).fill(0))

    for (let i = 0; i < m; i++) {
        if (obstacleGrid[i][0] === 1) {
            break
        }
        dp[i][0] = 1
    }
    for (let i = 0; i < n; i++) {
        if (obstacleGrid[0][i] === 1) {
            break
        }
        dp[0][i] = 1
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                continue
            }
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
}

let obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
console.log(uniquePathsWithObstacles(obstacleGrid));